package main

//n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
//
//
//
//
//
// 示例 1：
//
//
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= n <= 9
//
//
//
// Related Topics 回溯 👍 340 👎 0

//leetcode submit region begin(Prohibit modification and deletion)

var num int

func totalNQueens(n int) int {
	num = 0
	backTrack2(n, 0, make([]int, n), make([]int, 2*n), make([]int, 2*n))
	return num
}

func backTrack2(n, row int, columns, dia1, dia2 []int) {
	if n == row {
		num++
		return
	}
	for i := 0; i < n; i++ {
		if columns[i] == 1 {
			continue
		}
		// -n < row-i < n => 0 < row-i+n < 2n
		if dia1[row-i+n] == 1 {
			continue
		}
		// -1 < row+i < 2*n
		if dia2[row+i] == 1 {
			continue
		}
		columns[i], dia1[row-i+n], dia2[row+i] = 1, 1, 1
		backTrack2(n, row+1, columns, dia1, dia2)
		columns[i], dia1[row-i+n], dia2[row+i] = 0, 0, 0
	}
}

//leetcode submit region end(Prohibit modification and deletion)
